
// https://www.bilibili.com/video/BV1zz4y1m7Nq
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "hdf_spf.h"


//具有n个节点的spf算法，节点的编号为数组下标，从0开始
// distance用于存储0号节点到其它节点的最短距离
// last用于存储最短路径上，当前节点的前一个节点
// edge为每一个边的距离数组，元素与边的关系为。边(i,j)即节点i和节点j之间的距离为edge[i*n+j] i<j
// 当i >= j时，对应的edge元素为0
void spf(unsigned *edge, int n)
{
    unsigned *distance, *last, *checked;
    unsigned checked_count = 0;

    distance = (unsigned*)malloc(sizeof(unsigned) * n);
    last = (unsigned*)malloc(sizeof(unsigned)*n);
    checked = (unsigned*)malloc(sizeof(unsigned)*n);
    if(distance == NULL || last == NULL || checked == NULL)
        return;

    //edge和n由外部输入，distance和last在此处初始化，本算法主要计算0号节点到其它节点的最短路径
    distance[0] = 0;
    for(int i=1; i<n; i++)
        distance[i] = INF;

    for(int i=0; i<n; i++) {
        last[i] = INF;
        checked[i] = 0;
    }

    while(checked_count < n) {
        //从还未标记的节点中找出最小路径的节点
        unsigned min = INF;
        unsigned min_index = INF;
        for(int i=0; i<n; i++)
        {
            if(checked[i] == 0 && distance[i] < min)
            {
                min = distance[i];
                min_index = i;
            }
        }
        //针对找出的此节点做上标记
        checked[min_index] = 1;
        checked_count++;

        //进一步考虑与此节点相连的边
        for( int i=0; i<n; i++)
        {
            if(i == min_index)
                continue;
            unsigned edge_temp = (min_index < i ? edge[min_index * n + i] : edge[ i * n + min_index]);
            if(checked[i] == 0 
            && edge_temp > 0
            && distance[min_index] + edge_temp < distance[i])
            {
                distance[i] = distance[min_index] + edge_temp;
                last[i] = min_index;
            }
        }

    }  //所有的节点标记完毕，则所有节点到节点0的最短路径确定

    //输出每个节点到0号节点的最短路径
    for(int i=1; i<n; i++)
    {
        printf("第%d个节点的最短距离为%3d, 路径为: ", i, distance[i]);
        int j = i;
        printf("%d", i);
        while(last[j] != 0) {
            printf("<--%d", last[j]);
            j = last[j];                        
        }
        printf("<--0\n");         
    }    
}

